package 二叉树.大根堆.大根堆二叉树;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/10/12 9:02
 * @description:
 * @version:
 */
public class Solution {
    public static TreeNode createMaxHeapTree(int[] A,int n) {
        //2/n - 1可以找到完全二叉树的倒数第一个非叶子节点在数组中对应的下标
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(A, n, i);
        }
        return buildTree(A, 0);
    }
    /**
     * n表示数组的长度，i表示当前节点的索引
     */
    private static void heapify(int[] A, int n, int i) {
        int largest = i;
        //左孩子节点在数组对应的下标
        int left = 2 * i + 1;
        //右孩子节点在数组中对应的下标
        int right = 2 * i + 2;

        if (left < n && A[left] > A[largest]) {
            largest = left;
        }

        if (right < n && A[right] > A[largest]) {
            largest = right;
        }

        //largest != i说明需要进行交换了
        if (largest != i) {
            //交换元素
            int temp = A[i];
            A[i] = A[largest];
            A[largest] = temp;
            //递归
            heapify(A, n, largest);
        }
    }
    //根据数组构建出一个完全二叉树（此时数组已经被调整过了，这时构建的二叉树一定是完全二叉树）
    private static TreeNode buildTree(int[] A, int index) {
        if (index >= A.length) {
            return null;
        }
        TreeNode node = new TreeNode(A[index]);
        node.left = buildTree(A, 2 * index + 1);
        node.right = buildTree(A, 2 * index + 2);
        return node;
    }

    public static void main(String[] args) {
        int[] A = {0,1,2,3,4,5,6,7,8,9};
        int n = A.length;
        TreeNode root = createMaxHeapTree(A,n);
       // int min = getMin(root);
        System.out.println("Max Heap Tree created!");
    }

    /**
     * int getMin(BTNode* root) {
     *     if (root == nullptr) {
     *         return INT_MAX; // 返回最大整数作为初始最小值
     *     }
     *
     *     int minValue = root->data;
     *     int leftMin = getMin(root->left);
     *     int rightMin = getMin(root->right);
     *
     *     if (leftMin < minValue) {
     *         minValue = leftMin;
     *     }
     *     if (rightMin < minValue) {
     *         minValue = rightMin;
     *     }
     *
     *     return minValue;
     * }
     */

    public static int getMin(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        int minValue = root.val;
        int leftMin = getMin(root.left);
        int rightMin = getMin(root.right);
        if (leftMin < minValue) {
            minValue = leftMin;
        }
        if (rightMin < minValue) {
            minValue = rightMin;
        }
        return minValue;
    }


}
